friendsOfFriends(d) [30 pts]
This function is not recursive. Background: we can create a dictionary mapping people to sets of their friends. For example, we might say:
d = { }
d["spongebob"] = set(["sandy", "patrick", "mr.krabs", "squidward"])
d["mr.krabs"] = set(["pearl", "spongebob", "squidward"])
d["pearl"] = set(["mr.krabs"])
d["sandy"] = set(["spongebob", "patrick"])
d["patrick"] = set(["spongebob", "sandy"])
d["squidward"] = set()
With this in mind, write the function friendsOfFriends(d) that takes such a dictionary mapping people to sets of friends and returns a new dictionary mapping all the same people to sets of their friends of friends. For example, since Spongebob is a friend of Patrick, and Squidward is a friend of Spongebob, Squidward is a friend-of-friend of Patrick. This set should exclude any direct friends, so Sandy does not count as a friend-of-friend of Patrick (since she is simply a friend of Patrick) despite also being a friend of Spongebob's.
Thus, in this example, friendsOfFriends should return:
{
'spongebob': {'pearl'},
'mr.krabs': {'patrick', 'sandy'},
'pearl': {'spongebob', 'squidward'},
'sandy': {'mr.krabs', 'squidward'},
'patrick': {'mr.krabs', 'squidward'},
'squidward': set(),
}
Note 1: your function should not modify the initial provided dictionary!
Note 2: you may assume that everyone listed in any of the friend sets also is included as a key in the dictionary.
Note 3: you may assume that a person will never be included in their own friend set. You should also not include people in their own friends-of-friends sets!
Note 4: you may not assume that if Person1 lists Person2 as a friend, Person2 will list Person1 as a friend! Sometimes friendships are only one-way. =(
solveABC(constraints, aLocation) [35 pts]
This problem is inspired by the "ABC Path" problems at BrainBashers.com. For more (optional) info,
check this out. In what we will call an "ABC Puzzle", you are given a 5x5 board like this:
It is an empty board except that it contains a single "A" in an arbitrary cell. Also, the letters from "B" to "Y" are arranged around the outside of the board in an arbitrary order, along with arrows that constrain those letters to a certain row, column, or diagonal. For example, in the image, we see the "H" and "T" are constrained to column 0, "L" and "I" are constrained to row 0, and "C" and "G" are constrained to the column running from (0,0) to (4,4). The goal of this puzzle is to place every letter from "B" to "Y" on the board such that: (1) each letter from "B" to "Y" is placed in the row, column, or diagonal in which it is constrained; and (2) each letter from "B" to "Y" is placed adjacent (including diagonally) to the previous letter (so "B" is adjacent to "A", and "C" is adjacent to "B", and so on).
A solution to the puzzle shown above is:
Be sure you understand why this solves the puzzle! If you are unsure, go to the link at BrainBashers.com and read more about this kind of puzzle, including this help page, and maybe try to solve a few more of them (the puzzles include a button you can press to get the solutions!).
Now, for us to represent one of these puzzles in Python, we have to represent the constraints. We'll do that using a dictionary. The dictionary will have three keys: "rows", "cols", and "diags". "rows" and "cols" will each map to another dictionary which maps indexes of rows/cols to lists of the letters constrained to that row/col. "diags" will map to another dictionary that has two keys, "left" and "right", which map to the letters constrained to the left-down and right-down diagonals. Thus, in the given example, the constraints are:
constraints = {
"rows" : {
0 : ["I", "L"],
1 : ["M", "F"],
2 : ["Y", "N"],
3 : ["D", "U"],
4 : ["Q", "R"]
},
"cols" : {
0 : ["H", "T"],
1 : ["J", "W"],
2 : ["X", "K"],
3 : ["B", "E"],
4 : ["O", "P"]
},
"diags" : {
"left" : ["C", "G"],
"right" : ["V", "S"]
}
}
We also need to specify the position of the "A", which we will do as a (row,col) tuple, as such:
aLocation = (0,4)
With this in mind, write the function solveABC(constraints, aLocation), that takes constraints and the location of the "A", which together define an ABC Puzzle, and returns a completed board which solves the puzzle, or None if no such board exists. Here is a test function that is based on the puzzle used in the example above (notice how the constraints and aLocation match the unsolved puzzle, and the resulting board matches the solved puzzle):
def testSolveABC():
print('Testing solveABC()...', end='')
constraints = {
"rows" : { 0 : ["I", "L"],
1 : ["M", "F"],
2 : ["Y", "N"],
3 : ["D", "U"],
4 : ["Q", "R"] },
"cols" : { 0 : ["H", "T"],
1 : ["J", "W"],
2 : ["X", "K"],
3 : ["B", "E"],
4 : ["O", "P"] },
"diags" : { "left" : ["C", "G"],
"right" : ["V", "S"] } }
aLocation = (0,4)
board = solveABC(constraints, aLocation)
solution = [ ['I', 'J', 'K', 'L', 'A'],
['H', 'G', 'F', 'B', 'M'],
['T', 'Y', 'C', 'E', 'N'],
['U', 'S', 'X', 'D', 'O'],
['V', 'W', 'R', 'Q', 'P'] ]
assert(board == solution)
print('Passed!')
Notes/Hints:
- To receive any credit for this problem, you must solve it recursively, even if you could dream up a non-recursive solution!
- This is a backtracking problem. Study the backtracking template and backtracking examples; they will help.
- You will want to make judicious use of a helper function or optional parameters.